package Hard;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//30.串联所有单词的子串
public class Solution30 {
    public static List<Integer> findSubstring(String s, String[] words) {
        List<Integer> list = new ArrayList<>();
        int len = words[0].length();
        for (int i = 0; i <= s.length()-words.length*len; i++) {
            //复制一份words，防止对原数组直接进行操作
            String[] word = Arrays.copyOf(words, words.length);
            int count = word.length;
            int k = i;
            //直到找到word里所有单词循环才结束，如果循环提前结束，则说明本次以i开头的单词不能满足要求
            while (count > 0) {
                //每次从剩余数组里的元素寻找是否存在该元素。
                int j;
                boolean valid = false;
                for (j = 0; j < count; j++) {
                    if (word[j].equals(s.substring(k, k + len))) {
                        k += len;
                        word[j] = word[--count];
                        valid=true;
                        break;
                    }
                }
                //如果word里没有s.substring(k,k+len),则直接i++
                if (!valid) {
                    break;
                } else {
                    j = 0;
                }
            }
            if(count == 0){
                //存i
                list.add(i);
            }
        }
        return list;
    }

    public static void main(String[] args) {
        String[] str = new String[]{"fooo","barr","wing","ding","wing"};
        List<Integer> list = findSubstring("lingmindraboofooowingdingbarrwingmonkeypoundcake", str);
        for(int i :list){
            System.out.print(i+" ");
        }
    }
}
